package com.rui.study.algorithm.P_删除链表倒数第n个节点;

import com.rui.study.algorithm.ListNode;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2019-01-11 10:13
 **/
public class Solution {

    /**
     * 思路：使用双指针p和t，双指针距离相差n，当t到达链表尾节点时，p指针到达待删除节点的父节点，
     * 这时候p.next = p.next.next即可；另一种情况当n等于链表长度的时候，去掉头节点即可。
     * 时间复杂度为O(n)
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;
        ListNode t = head;
        ListNode p = head;
        int len = 0;
        while (t.next != null) {
            t = t.next;
            if (++len > n) {
                p = p.next;
            }
        }
        len++;
        ListNode tmp;
        if (n == len) {
            tmp = head.next;
            head.next = null;
            head = tmp;
        } else {
            p.next = p.next.next;
        }
        return head;
    }
}
